/*-------------------------------------------------------------*/
/*--- Decompression machinery                               ---*/
/*---                                          decompress.c ---*/
/*-------------------------------------------------------------*/

/* ------------------------------------------------------------------
   This file is part of bzip2/libbzip2, a program and library for
   lossless, block-sorting data compression.

   bzip2/libbzip2 version 1.0.6 of 6 September 2010
   Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>

   Please read the WARNING, DISCLAIMER and PATENTS sections in the 
   README file.

   This program is released under the terms of the license contained
   in the file LICENSE.
   ------------------------------------------------------------------ */


#include "bzlib_private.h"


/*---------------------------------------------------*/
static
void makeMaps_d(DState *s) {
    Int32 i;
    s->nInUse = 0;
    for (i = 0; i < 256; i++)
        if (s->inUse[i]) {
            s->seqToUnseq[s->nInUse] = i;
            s->nInUse++;
        }
}


/*---------------------------------------------------*/
#define RETURN(rrr)                               \
   { retVal = rrr; goto save_state_and_return; };

#define GET_BITS(lll, vvv, nnn)                     \
   case lll: s->state = lll;                      \
   while (True) {                                 \
      if (s->bsLive >= nnn) {                     \
         UInt32 v;                                \
         v = (s->bsBuff >>                        \
             (s->bsLive-nnn)) & ((1 << nnn)-1);   \
         s->bsLive -= nnn;                        \
         vvv = v;                                 \
         break;                                   \
      }                                           \
      if (s->strm->avail_in == 0) RETURN(BZ_OK);  \
      s->bsBuff                                   \
         = (s->bsBuff << 8) |                     \
           ((UInt32)                              \
              (*((UChar*)(s->strm->next_in))));   \
      s->bsLive += 8;                             \
      s->strm->next_in++;                         \
      s->strm->avail_in--;                        \
      s->strm->total_in_lo32++;                   \
      if (s->strm->total_in_lo32 == 0)            \
         s->strm->total_in_hi32++;                \
   }

#define GET_UCHAR(lll, uuu)                        \
   GET_BITS(lll,uuu,8)

#define GET_BIT(lll, uuu)                          \
   GET_BITS(lll,uuu,1)

/*---------------------------------------------------*/
#define GET_MTF_VAL(label1, label2, lval)           \
{                                                 \
   if (groupPos == 0) {                           \
      groupNo++;                                  \
      if (groupNo >= nSelectors)                  \
         RETURN(BZ_DATA_ERROR);                   \
      groupPos = BZ_G_SIZE;                       \
      gSel = s->selector[groupNo];                \
      gMinlen = s->minLens[gSel];                 \
      gLimit = &(s->limit[gSel][0]);              \
      gPerm = &(s->perm[gSel][0]);                \
      gBase = &(s->base[gSel][0]);                \
   }                                              \
   groupPos--;                                    \
   zn = gMinlen;                                  \
   GET_BITS(label1, zvec, zn);                    \
   while (1) {                                    \
      if (zn > 20 /* the longest code */)         \
         RETURN(BZ_DATA_ERROR);                   \
      if (zvec <= gLimit[zn]) break;              \
      zn++;                                       \
      GET_BIT(label2, zj);                        \
      zvec = (zvec << 1) | zj;                    \
   };                                             \
   if (zvec - gBase[zn] < 0                       \
       || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE)  \
      RETURN(BZ_DATA_ERROR);                      \
   lval = gPerm[zvec - gBase[zn]];                \
}


/*---------------------------------------------------*/
Int32 BZ2_decompress(DState *s) {
    UChar uc;
    Int32 retVal;
    Int32 minLen, maxLen;
    bz_stream *strm = s->strm;

    /* stuff that needs to be saved/restored */
    Int32 i;
    Int32 j;
    Int32 t;
    Int32 alphaSize;
    Int32 nGroups;
    Int32 nSelectors;
    Int32 EOB;
    Int32 groupNo;
    Int32 groupPos;
    Int32 nextSym;
    Int32 nblockMAX;
    Int32 nblock;
    Int32 es;
    Int32 N;
    Int32 curr;
    Int32 zt;
    Int32 zn;
    Int32 zvec;
    Int32 zj;
    Int32 gSel;
    Int32 gMinlen;
    Int32 *gLimit;
    Int32 *gBase;
    Int32 *gPerm;

    if (s->state == BZ_X_MAGIC_1) {
        /*initialise the save area*/
        s->save_i = 0;
        s->save_j = 0;
        s->save_t = 0;
        s->save_alphaSize = 0;
        s->save_nGroups = 0;
        s->save_nSelectors = 0;
        s->save_EOB = 0;
        s->save_groupNo = 0;
        s->save_groupPos = 0;
        s->save_nextSym = 0;
        s->save_nblockMAX = 0;
        s->save_nblock = 0;
        s->save_es = 0;
        s->save_N = 0;
        s->save_curr = 0;
        s->save_zt = 0;
        s->save_zn = 0;
        s->save_zvec = 0;
        s->save_zj = 0;
        s->save_gSel = 0;
        s->save_gMinlen = 0;
        s->save_gLimit = NULL;
        s->save_gBase = NULL;
        s->save_gPerm = NULL;
    }

    /*restore from the save area*/
    i = s->save_i;
    j = s->save_j;
    t = s->save_t;
    alphaSize = s->save_alphaSize;
    nGroups = s->save_nGroups;
    nSelectors = s->save_nSelectors;
    EOB = s->save_EOB;
    groupNo = s->save_groupNo;
    groupPos = s->save_groupPos;
    nextSym = s->save_nextSym;
    nblockMAX = s->save_nblockMAX;
    nblock = s->save_nblock;
    es = s->save_es;
    N = s->save_N;
    curr = s->save_curr;
    zt = s->save_zt;
    zn = s->save_zn;
    zvec = s->save_zvec;
    zj = s->save_zj;
    gSel = s->save_gSel;
    gMinlen = s->save_gMinlen;
    gLimit = s->save_gLimit;
    gBase = s->save_gBase;
    gPerm = s->save_gPerm;

    retVal = BZ_OK;

    switch (s->state) {

        GET_UCHAR(BZ_X_MAGIC_1, uc);
        if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);

        GET_UCHAR(BZ_X_MAGIC_2, uc);
        if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);

        GET_UCHAR(BZ_X_MAGIC_3, uc)
        if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);

        GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
        if (s->blockSize100k<(BZ_HDR_0 + 1) ||
                             s->blockSize100k>(BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
        s->blockSize100k -= BZ_HDR_0;

        if (s->smallDecompress) {
            s->ll16 = BZALLOC(s->blockSize100k * 100000 * sizeof(UInt16));
            s->ll4 = BZALLOC(
                    ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
            );
            if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
        } else {
            s->tt = BZALLOC(s->blockSize100k * 100000 * sizeof(Int32));
            if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
        }

        GET_UCHAR(BZ_X_BLKHDR_1, uc);

        if (uc == 0x17) goto endhdr_2;
        if (uc != 0x31) RETURN(BZ_DATA_ERROR);
        GET_UCHAR(BZ_X_BLKHDR_2, uc);
        if (uc != 0x41) RETURN(BZ_DATA_ERROR);
        GET_UCHAR(BZ_X_BLKHDR_3, uc);
        if (uc != 0x59) RETURN(BZ_DATA_ERROR);
        GET_UCHAR(BZ_X_BLKHDR_4, uc);
        if (uc != 0x26) RETURN(BZ_DATA_ERROR);
        GET_UCHAR(BZ_X_BLKHDR_5, uc);
        if (uc != 0x53) RETURN(BZ_DATA_ERROR);
        GET_UCHAR(BZ_X_BLKHDR_6, uc);
        if (uc != 0x59) RETURN(BZ_DATA_ERROR);

        s->currBlockNo++;
        if (s->verbosity >= 2)
            VPrintf1 ("\n    [%d: huff+mtf ", s->currBlockNo);

        s->storedBlockCRC = 0;
        GET_UCHAR(BZ_X_BCRC_1, uc);
        s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32) uc);
        GET_UCHAR(BZ_X_BCRC_2, uc);
        s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32) uc);
        GET_UCHAR(BZ_X_BCRC_3, uc);
        s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32) uc);
        GET_UCHAR(BZ_X_BCRC_4, uc);
        s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32) uc);

        GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);

        s->origPtr = 0;
        GET_UCHAR(BZ_X_ORIGPTR_1, uc);
        s->origPtr = (s->origPtr << 8) | ((Int32) uc);
        GET_UCHAR(BZ_X_ORIGPTR_2, uc);
        s->origPtr = (s->origPtr << 8) | ((Int32) uc);
        GET_UCHAR(BZ_X_ORIGPTR_3, uc);
        s->origPtr = (s->origPtr << 8) | ((Int32) uc);

        if (s->origPtr < 0) RETURN(BZ_DATA_ERROR);
        if (s->origPtr > 10 + 100000 * s->blockSize100k) RETURN(BZ_DATA_ERROR);

        /*--- Receive the mapping table ---*/
        for (i = 0; i < 16; i++) {
            GET_BIT(BZ_X_MAPPING_1, uc);
            if (uc == 1)
                s->inUse16[i] = True;
            else
                s->inUse16[i] = False;
        }

        for (i = 0; i < 256; i++) s->inUse[i] = False;

        for (i = 0; i < 16; i++)
            if (s->inUse16[i])
                for (j = 0; j < 16; j++) {
                    GET_BIT(BZ_X_MAPPING_2, uc);
                    if (uc == 1) s->inUse[i * 16 + j] = True;
                }
        makeMaps_d(s);
        if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
        alphaSize = s->nInUse + 2;

        /*--- Now the selectors ---*/
        GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
        if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
        GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
        if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
        for (i = 0; i < nSelectors; i++) {
            j = 0;
            while (True) {
                GET_BIT(BZ_X_SELECTOR_3, uc);
                if (uc == 0) break;
                j++;
                if (j >= nGroups) RETURN(BZ_DATA_ERROR);
            }
            s->selectorMtf[i] = j;
        }

        /*--- Undo the MTF values for the selectors. ---*/
        {
            UChar pos[BZ_N_GROUPS], tmp, v;
            for (v = 0; v < nGroups; v++) pos[v] = v;

            for (i = 0; i < nSelectors; i++) {
                v = s->selectorMtf[i];
                tmp = pos[v];
                while (v > 0) {
                    pos[v] = pos[v - 1];
                    v--;
                }
                pos[0] = tmp;
                s->selector[i] = tmp;
            }
        }

        /*--- Now the coding tables ---*/
        for (t = 0; t < nGroups; t++) {
            GET_BITS(BZ_X_CODING_1, curr, 5);
            for (i = 0; i < alphaSize; i++) {
                while (True) {
                    if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
                    GET_BIT(BZ_X_CODING_2, uc);
                    if (uc == 0) break;
                    GET_BIT(BZ_X_CODING_3, uc);
                    if (uc == 0) curr++; else curr--;
                }
                s->len[t][i] = curr;
            }
        }

        /*--- Create the Huffman decoding tables ---*/
        for (t = 0; t < nGroups; t++) {
            minLen = 32;
            maxLen = 0;
            for (i = 0; i < alphaSize; i++) {
                if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
                if (s->len[t][i] < minLen) minLen = s->len[t][i];
            }
            BZ2_hbCreateDecodeTables(
                    &(s->limit[t][0]),
                    &(s->base[t][0]),
                    &(s->perm[t][0]),
                    &(s->len[t][0]),
                    minLen, maxLen, alphaSize
            );
            s->minLens[t] = minLen;
        }

        /*--- Now the MTF values ---*/

        EOB = s->nInUse + 1;
        nblockMAX = 100000 * s->blockSize100k;
        groupNo = -1;
        groupPos = 0;

        for (i = 0; i <= 255; i++) s->unzftab[i] = 0;

        /*-- MTF init --*/
        {
            Int32 ii, jj, kk;
            kk = MTFA_SIZE - 1;
            for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
                for (jj = MTFL_SIZE - 1; jj >= 0; jj--) {
                    s->mtfa[kk] = (UChar) (ii * MTFL_SIZE + jj);
                    kk--;
                }
                s->mtfbase[ii] = kk + 1;
            }
        }
        /*-- end MTF init --*/

        nblock = 0;
        GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);

        while (True) {

            if (nextSym == EOB) break;

            if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {

                es = -1;
                N = 1;
                do {
                    /* Check that N doesn't get too big, so that es doesn't
                       go negative.  The maximum value that can be
                       RUNA/RUNB encoded is equal to the block size (post
                       the initial RLE), viz, 900k, so bounding N at 2
                       million should guard against overflow without
                       rejecting any legitimate inputs. */
                    if (N >= 2 * 1024 * 1024) RETURN(BZ_DATA_ERROR);
                    if (nextSym == BZ_RUNA) es = es + (0 + 1) * N; else if (nextSym == BZ_RUNB)
                        es = es + (1 + 1) * N;
                    N = N * 2;
                    GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
                }
                while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);

                es++;
                uc = s->seqToUnseq[s->mtfa[s->mtfbase[0]]];
                s->unzftab[uc] += es;

                if (s->smallDecompress)
                    while (es > 0) {
                        if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
                        s->ll16[nblock] = (UInt16) uc;
                        nblock++;
                        es--;
                    }
                else
                    while (es > 0) {
                        if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
                        s->tt[nblock] = (UInt32) uc;
                        nblock++;
                        es--;
                    };

                continue;

            } else {

                if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);

                /*-- uc = MTF ( nextSym-1 ) --*/
                {
                    Int32 ii, jj, kk, pp, lno, off;
                    UInt32 nn;
                    nn = (UInt32) (nextSym - 1);

                    if (nn < MTFL_SIZE) {
                        /* avoid general-case expense */
                        pp = s->mtfbase[0];
                        uc = s->mtfa[pp + nn];
                        while (nn > 3) {
                            Int32 z = pp + nn;
                            s->mtfa[(z)] = s->mtfa[(z) - 1];
                            s->mtfa[(z) - 1] = s->mtfa[(z) - 2];
                            s->mtfa[(z) - 2] = s->mtfa[(z) - 3];
                            s->mtfa[(z) - 3] = s->mtfa[(z) - 4];
                            nn -= 4;
                        }
                        while (nn > 0) {
                            s->mtfa[(pp + nn)] = s->mtfa[(pp + nn) - 1];
                            nn--;
                        };
                        s->mtfa[pp] = uc;
                    } else {
                        /* general case */
                        lno = nn / MTFL_SIZE;
                        off = nn % MTFL_SIZE;
                        pp = s->mtfbase[lno] + off;
                        uc = s->mtfa[pp];
                        while (pp > s->mtfbase[lno]) {
                            s->mtfa[pp] = s->mtfa[pp - 1];
                            pp--;
                        };
                        s->mtfbase[lno]++;
                        while (lno > 0) {
                            s->mtfbase[lno]--;
                            s->mtfa[s->mtfbase[lno]]
                                    = s->mtfa[s->mtfbase[lno - 1] + MTFL_SIZE - 1];
                            lno--;
                        }
                        s->mtfbase[0]--;
                        s->mtfa[s->mtfbase[0]] = uc;
                        if (s->mtfbase[0] == 0) {
                            kk = MTFA_SIZE - 1;
                            for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
                                for (jj = MTFL_SIZE - 1; jj >= 0; jj--) {
                                    s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
                                    kk--;
                                }
                                s->mtfbase[ii] = kk + 1;
                            }
                        }
                    }
                }
                /*-- end uc = MTF ( nextSym-1 ) --*/

                s->unzftab[s->seqToUnseq[uc]]++;
                if (s->smallDecompress)
                    s->ll16[nblock] = (UInt16) (s->seqToUnseq[uc]);
                else
                    s->tt[nblock] = (UInt32) (s->seqToUnseq[uc]);
                nblock++;

                GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
                continue;
            }
        }

        /* Now we know what nblock is, we can do a better sanity
           check on s->origPtr.
        */
        if (s->origPtr < 0 || s->origPtr >= nblock) RETURN(BZ_DATA_ERROR);

        /*-- Set up cftab to facilitate generation of T^(-1) --*/
        /* Check: unzftab entries in range. */
        for (i = 0; i <= 255; i++) {
            if (s->unzftab[i] < 0 || s->unzftab[i] > nblock) RETURN(BZ_DATA_ERROR);
        }
        /* Actually generate cftab. */
        s->cftab[0] = 0;
        for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i - 1];
        for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i - 1];
        /* Check: cftab entries in range. */
        for (i = 0; i <= 256; i++) {
            if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
                /* s->cftab[i] can legitimately be == nblock */
                RETURN(BZ_DATA_ERROR);
            }
        }
        /* Check: cftab entries non-descending. */
        for (i = 1; i <= 256; i++) {
            if (s->cftab[i - 1] > s->cftab[i]) {
                RETURN(BZ_DATA_ERROR);
            }
        }

        s->state_out_len = 0;
        s->state_out_ch = 0;
        BZ_INITIALISE_CRC (s->calculatedBlockCRC);
        s->state = BZ_X_OUTPUT;
        if (s->verbosity >= 2) VPrintf0 ("rt+rld");

        if (s->smallDecompress) {

            /*-- Make a copy of cftab, used in generation of T --*/
            for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];

            /*-- compute the T vector --*/
            for (i = 0; i < nblock; i++) {
                uc = (UChar) (s->ll16[i]);
                SET_LL(i, s->cftabCopy[uc]);
                s->cftabCopy[uc]++;
            }

            /*-- Compute T^(-1) by pointer reversal on T --*/
            i = s->origPtr;
            j = GET_LL(i);
            do {
                Int32 tmp = GET_LL(j);
                SET_LL(j, i);
                i = j;
                j = tmp;
            }
            while (i != s->origPtr);

            s->tPos = s->origPtr;
            s->nblock_used = 0;
            if (s->blockRandomised) {
                BZ_RAND_INIT_MASK;
                BZ_GET_SMALL(s->k0);
                s->nblock_used++;
                BZ_RAND_UPD_MASK;
                s->k0 ^= BZ_RAND_MASK;
            } else {
                BZ_GET_SMALL(s->k0);
                s->nblock_used++;
            }

        } else {

            /*-- compute the T^(-1) vector --*/
            for (i = 0; i < nblock; i++) {
                uc = (UChar) (s->tt[i] & 0xff);
                s->tt[s->cftab[uc]] |= (i << 8);
                s->cftab[uc]++;
            }

            s->tPos = s->tt[s->origPtr] >> 8;
            s->nblock_used = 0;
            if (s->blockRandomised) {
                BZ_RAND_INIT_MASK;
                BZ_GET_FAST(s->k0);
                s->nblock_used++;
                BZ_RAND_UPD_MASK;
                s->k0 ^= BZ_RAND_MASK;
            } else {
                BZ_GET_FAST(s->k0);
                s->nblock_used++;
            }

        }

        RETURN(BZ_OK);


        endhdr_2:

        GET_UCHAR(BZ_X_ENDHDR_2, uc);
            if (uc != 0x72) RETURN(BZ_DATA_ERROR);
        GET_UCHAR(BZ_X_ENDHDR_3, uc);
            if (uc != 0x45) RETURN(BZ_DATA_ERROR);
        GET_UCHAR(BZ_X_ENDHDR_4, uc);
            if (uc != 0x38) RETURN(BZ_DATA_ERROR);
        GET_UCHAR(BZ_X_ENDHDR_5, uc);
            if (uc != 0x50) RETURN(BZ_DATA_ERROR);
        GET_UCHAR(BZ_X_ENDHDR_6, uc);
            if (uc != 0x90) RETURN(BZ_DATA_ERROR);

            s->storedCombinedCRC = 0;
        GET_UCHAR(BZ_X_CCRC_1, uc);
            s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32) uc);
        GET_UCHAR(BZ_X_CCRC_2, uc);
            s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32) uc);
        GET_UCHAR(BZ_X_CCRC_3, uc);
            s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32) uc);
        GET_UCHAR(BZ_X_CCRC_4, uc);
            s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32) uc);

            s->state = BZ_X_IDLE;
            RETURN(BZ_STREAM_END);

        default: AssertH (False, 4001);
    }

    AssertH (False, 4002);

    save_state_and_return:

    s->save_i = i;
    s->save_j = j;
    s->save_t = t;
    s->save_alphaSize = alphaSize;
    s->save_nGroups = nGroups;
    s->save_nSelectors = nSelectors;
    s->save_EOB = EOB;
    s->save_groupNo = groupNo;
    s->save_groupPos = groupPos;
    s->save_nextSym = nextSym;
    s->save_nblockMAX = nblockMAX;
    s->save_nblock = nblock;
    s->save_es = es;
    s->save_N = N;
    s->save_curr = curr;
    s->save_zt = zt;
    s->save_zn = zn;
    s->save_zvec = zvec;
    s->save_zj = zj;
    s->save_gSel = gSel;
    s->save_gMinlen = gMinlen;
    s->save_gLimit = gLimit;
    s->save_gBase = gBase;
    s->save_gPerm = gPerm;

    return retVal;
}


/*-------------------------------------------------------------*/
/*--- end                                      decompress.c ---*/
/*-------------------------------------------------------------*/
